package com.zk.algorithm.linkedlist;

import com.zk.algorithm.bean.ListNode;

/**
 * @author zk
 */
public class RotateList {

    // 1->2->3->4->5->NULL, k = 2
    //
    // 5->1->2->3->4->NULL
    // 4->5->1->2->3->NULL
    //
    // 1. 找到前半截、后半截分割节点
    // 2. 后半截连接前半截成环
    // 3. 后半截成为头节点
    // 4. 前半截、后半截断开
    public ListNode rotateRight(ListNode head, int k) {
        ListNode dummy = new ListNode(-1),
                slow = dummy,
                fast = dummy;
        dummy.next = head;

        // ===================
        // 统计长度
        // ===================

        int len = 0;
        // DUMMY -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
        //                              ↑
        while (fast.next != null) {   // fast REACH tail && Count len
            fast = fast.next;
            len++;
        }
        if (len == 0) return null;   // CHECK null

        k %= len;
        // 1->2->3->4->5->NULL
        //
        // DUMMY -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
        //                    ↑
        for (int i = 0; i < len - k; i++)  // slow REACH before the rotated point
            slow = slow.next;

        // 搞成环
        //                   slow
        //                    ↓
        // DUMMY -> 1 -> 2 -> 3 -> 4 -> 5 <- fast
        //          ↑___________________|
        //
        fast.next = dummy.next;      // CONNECT

        //
        //   |---------------------|
        //   |                     |
        //   |               slow  |
        //   |                ↓    ↓
        // DUMMY    1 -> 2 -> 3 -> 4 -> 5 <- fast
        //          ↑___________________|
        //
        dummy.next = slow.next;

        //
        //   |---------------------|
        //   |                     |
        //   |               slow  |
        //   |                ↓    ↓
        // DUMMY    1 -> 2 -> 3    4 -> 5 <- fast
        //          ↑___________________|
        //
        slow.next = null;

        return dummy.next;
    }

}
